|
In graph theory, a connected component (or just component) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph. For example, the graph shown in the illustration on the right has three connected components. A vertex with no incident edges is itself a connected component. A graph that is itself connected has exactly one connected component, consisting of the whole graph. ==An equivalence relation== An alternative way to define connected components involves the equivalence classes of an equivalence relation that is defined on the vertices of the graph. In an undirected graph, a vertex ''v'' is ''reachable'' from a vertex ''u'' if there is a path from ''u'' to ''v''. In this definition, a single vertex is counted as a path of length zero, and the same vertex may occur more than once within a path. Reachability is an equivalence relation, since: *It is reflexive: There is a trivial path of length zero from any vertex to itself. *It is symmetric: If there is a path from ''u'' to ''v'', the same edges form a path from ''v'' to ''u''. *It is transitive: If there is a path from ''u'' to ''v'' and a path from ''v'' to ''w'', the two paths may be concatenated together to form a path from ''u'' to ''w''. The connected components are then the induced subgraphs formed by the equivalence classes of this relation. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Connected component (graph theory)」の詳細全文を読む スポンサード リンク
|